1
Dasar-Dasar Pendekatan Norm
MATH008Lesson 6
00:00
Bayangkan Anda seorang penjahit yang berusaha menyesuaikan setelan standar (ruang dari $A$) dengan klien yang memiliki proporsi unik (vektor $b$). Tidak peduli seberapa banyak Anda menyesuaikan lengan atau pinggang (koefisien $x$), setelan itu tidak akan pernah pas ketat seperti kulit. Anda sedang mencari kompromi "terbaik"—sebuah pendekatan norm yang meminimalkan ketegangan atau "sisa" di setiap jahitan.

Rangkaian Matematis

Tujuan utama adalah mencari vektor $x \in \mathbb{R}^n$ sehingga kombinasi linear $Ax = x_1a_1 + \dots + x_na_n$ paling mendekati $b$. Hal ini sering disebut sebagai regresi dari $b$ terhadap variabel regresi (kolom-kolom dari $A$).

Kita fokus pada vektor sisa $r = Ax - b$. Dalam praktiknya, kita mengasumsikan sistem yang sistem yang lebih banyak persamaan daripada variabel di mana $m > n$. Mengapa? Karena ketika $m = n$ dan $A$ tidak singular, titik optimalnya hanya $A^{-1}b$, menghasilkan kesalahan nol—kasus yang sangat sederhana dalam optimasi.

🎯 Prinsip Utama
Masalah pendekatan norm (6.1) adalah sebuah masalah konveks dan pasti dapat diselesaikan. Selalu ada setidaknya satu solusi optimal $\hat{x}$ yang meminimalkan jarak antara target dan ruang yang dapat dicapai.

Variasi Standar

Tergantung pada jenis kesalahan yang ingin kita hukum, kita memilih norma yang berbeda:

1. Kuadrat Terkecil ($\ell_2$ Norm)

Pendekatan paling umum. Ini meminimalkan jumlah kuadrat sisa: $\|Ax - b\|_2^2$. Ia sensitif terhadap outlier besar tetapi memberikan solusi analitik melalui persamaan normal.

2. Chebyshev / Minimax ($\ell_\infty$ Norm)

Meminimalkan maksimum absolut sisa $\max_i |r_i|$. Digunakan ketika setiap pengukuran harus tetap dalam toleransi ketat. Dapat diselesaikan melalui Program Linier (LP) berikut:

minimalkan $t$
dengan syarat $-t\mathbf{1} \preceq Ax - b \preceq t\mathbf{1}$

3. Jumlah Sisa Absolut ($\ell_1$ Norm)

Meminimalkan $\sum |r_i|$. Pendekatan ini tangguh terhadap outlier karena tidak mengkuadratkan kesalahan. Juga dapat diselesaikan melalui LP:

minimalkan $\mathbf{1}^T t$
dengan syarat $-t \preceq Ax - b \preceq t$

Konteks Estimasi

Dalam banyak bidang teknik, kita mengasumsikan keadaan sejati $x$ terhalang oleh gangguan: $y = Ax + v$. Tujuan kita adalah menemukan perkiraan $\hat{x} = \text{argmin}_z \|Az - y\|$. Dengan memilih norma, kita secara efektif membuat asumsi tentang distribusi statistik gangguan $v$.

\text{Minimalkan } \|u - b\| \text{ dengan syarat } u \in \mathcal{A} \quad (\text{di mana } \mathcal{A} = \text{Range}(A))